from math import inf
from typing import *


class Solution:

    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        dp = [[inf] * (n + 1) for _ in range(d + 1)]
        dp[0][0] = 0
        for i in range(1, d + 1):
            for j in range(i, n + 1):
                mx = 0
                for k in range(j, i - 1, -1):
                    mx = max(jobDifficulty[k - 1], mx)
                    dp[i][j] = min(dp[i][j], dp[i - 1][k - 1] + mx)
        return dp[d][n] if dp[d][n] != inf else -1


s = Solution()
print(s.minDifficulty(jobDifficulty=[6, 5, 4, 3, 2, 1], d=2))
